package com.wenhao.leetcode.hard;

import java.util.*;

/**
 * 题目：https://leetcode-cn.com/problems/word-ladder/
 * 单词接龙
 *
 * 从这一题里面学到了什么？
 * 1. 这一题首先看题目可以很直观地发现需要用到深度优先遍历
 * 2. 但是如何建立一张图是一个问题
 *      图的本质是一系列的节点被一系列的边连接起来
 *      那么我们要做的就是得到这一系列节点和这一系列的边
 *      节点很好办，使用HashMap逐一编号就可以快速查找到我们想要的字符串了
 *      边就复杂一点
 *      因为如果直接对比两个字符串的话需要遍历字符串的每一个字符，这样的时间复杂度是比较高的，所以这一题里面用到了一个中间节点来间接地把两个可以通过修改一个字符互相转化的字符串连接起来
 *      注意，这样经过广度优先遍历计算出的路径长度就需要除以二了
 *
 * 通过这一题，学会了如何建立一张图
 * 复习了如何进行广度优先遍历（迭代的方法，需要用到队列）
 * @author Wenhao Tong
 * @create 2021-07-11 13:14
 */
public class LeetCode127 {
    public static void main(String[] args) {

    }

    Map<String, Integer> wordId = new HashMap<String, Integer>();
    /**
     * 用于存放边的信息 即当前的节点是可以与哪些节点只差一个字母
     */
    List<List<Integer>> edge = new ArrayList<List<Integer>>();
    int nodeNum = 0;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 先使用HashMap对每一个word进行编号
        for (String word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.containsKey(endWord)) {
            return 0;
        }
        int[] dis = new int[nodeNum];
        Arrays.fill(dis,Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord) , endId = wordId.get(endWord);
        dis[beginId] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(beginId);
        while (queue.size() > 0) {
            int x = queue.poll();
            if (x == endId) {
                return dis[endId] / 2 + 1;
            }
            for (int i : edge.get(x)) {
                if (dis[i] == Integer.MAX_VALUE) {
                    dis[i] = dis[x] + 1;
                    queue.offer(i);
                }
            }
        }
        return 0;
    }

    private void addEdge(String word) {
        addWord(word);
        int id = wordId.get(word);
        char[] chars = word.toCharArray();
        for (int i = 0;i < chars.length;i++) {
            char c = chars[i];
            chars[i] = '*';
            String tempWord = new String(chars);
            addWord((tempWord));
            int newId = wordId.get(tempWord);
            // 举例 horse 与 ho*se 互相连接 house 也会与 ho*se 互相连接 这样通过ho*se这一个中间节点
            // 我们就可以不需要遍历整个 wordList 和 wordList 里面单词的每一个字母，也可以建立这两个单词之间的连接了
            edge.get(id).add(newId);
            edge.get(newId).add(id);
            chars[i] = c;
        }
    }

    // 添加一个之前没有出现过的单词
    private void addWord(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word,nodeNum++);
            edge.add(new ArrayList<>());
        }
    }
}
